package com.kevin.Code.Backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname GrayCode
 * @Description Leetcode 89. 格雷编码 中等难度 要再做
 * @Date 2021/10/31 17:35
 * @Version 1.0
 */
public class GrayCode {

    /**
     * 精选题解难以理解
     *
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {


        List<Integer> res = new ArrayList<Integer>() {{
            add(0);
        }};
        int head = 1;
        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                System.out.println(head + res.get(j));
                res.add(head + res.get(j));
            }

            head <<= 1;
        }
        return res;

    }

    /**
     * 格雷码的生成
     * 00^00 = 00
     * 01^00 = 01
     * 10^01==11
     *
     * @param n
     * @return
     */
    public List<Integer> grayCode1(int n) {

        //1向左移动几位
        //总的个数
        int totalNum = 1 << n;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < totalNum; i++) {

            result.add(i ^ i >> 1);
        }
        return result;
    }


    public static void main(String[] args) {
//        GrayCode grayCode = new GrayCode();
//       grayCode.grayCode(2);
        System.out.println(1 << 3);
    }
}
